package com.imooc.distributedemo.resume.leetcode;

/**
 * leetcode64  最小路劲和
 */
public class Solution64 {

    public static void main(String[] args) {
        int[][] grid = {
                {1,3,1},
                {1,5,1},
                {4,2,1},
                {8,4,2},
        };
        int result = minPathSum(grid);
        System.out.println(result);
    }

    /**
     * 创建二维数组 dp，与原始网格的大小相同，dp[i][j] 表示从左上角出发到 (i,j) 位置的最小路径和。显然，dp[0][0]=grid[0][0]。对于 dp 中的其余元素，通过以下状态转移方程计算元素值。
     *
     * 当 i>0 且 j=0 时，dp[i][0]=dp[i−1][0]+grid[i][0]。
     *
     * 当 i=0 且 j>0 时，dp[0][j]=dp[0][j−1]+grid[0][j]。
     *
     * 当 i>0 且 j>0 时，dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]
     *
     * @param grid
     * @return
     */
    public static int minPathSum(int[][] grid) {
        if(grid==null || grid.length==0 ||grid[0].length==0){
            return 0;
        }
        int rows = grid.length; // 获取行数
        int columns = grid[0].length; // 获取列数
        int[][] dp = new int[rows][columns]; // 声明二维数组
        dp[0][0] = grid[0][0]; // 初始化二维数组大小
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i-1][0] +grid[i][0];
        }

        for (int j = 1; j < columns; j++) {
            dp[0][j] = dp[0][j-1] +grid[0][j];
        }

        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                int left2right = dp[i-1][j];
                int up2down = dp[i][j-1];
                // 获取前一个：向右or向下的较小的那个值
                int preDat = Math.min(left2right,up2down);//dp[i-1][j]+dp[i][j-1];
                // 获取当前网格的值
                int curDat = grid[i][j];
                dp[i][j] = preDat+curDat;
            }
        }
        int result = dp[rows-1][columns-1];
        return result;
    }
}
